• 数据结构是指一组数据的存储结构，算法是操作数据的一组方法

• 数据结构是为算法服务的，算法要作用在特定的数据结构之上

• 常用的 20 个数据结构与算法

  • 10 个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树
  • 10 个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

复杂度分析

• 大 O 复杂度表示法 T(n) = O(f(n))

• 复杂度分析

  1. 只关注循环执行次数最多的一段代码
  2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
  3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

• 常见的复杂度级别

  • 多项式阶：随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长，包括：O(1)（常数阶）、O(logn)（对数阶）、O(n)（线性阶）、O(nlogn)（线性对数阶）、O(n^2^)（平方阶）、O(n^3^)（立方阶）、O(n^k^)（k 次方阶）
  • 非多项式阶：随着数据规模的增长，算法的执行时间和空间占用会急剧增加，这类算法性能极差，包括：O(2ⁿ)（指数阶）、O(n!)（阶乘阶）

  

• 时间复杂度（渐进时间复杂度），表示算法的执行时间与数据规模之间的增长关系

  • 常见时间复杂度：O(1)、O(logn)、O(nlogn)、O(m+n)、O(m*n)

  在小规模数据面前，O(n²) 时间复杂度的算法并不一定比 O(nlogn) 的算法执行时间长

• 空间复杂度（渐进空间复杂度），表示算法的存储空间与数据规模之间的增长关系

  • 常见的空间复杂度：O(1)、O(n)、O(n2 )
  • 空间复杂度是值除了原本的数据存储空间外，算法运行还需要额外的存储空间

• 同一段代码，在不同输入的情况下，复杂度量级有可能是不一样的，因此需要引入

  • 最好情况时间复杂度
  • 最坏情况时间复杂度
  • 平均时间复杂度，加权平均时间复杂度，期望时间复杂度，计算时需要考虑各种情况发生的概率
  • 均摊时间复杂度，对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，可以将这一组操作放在一块儿分析，将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上（摊还分析）

数组（Array）

• 数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据

• 数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)

• 但插入、删除操作比较低效，平均情况时间复杂度为 O(n)

• 寻址公式：a[i]_address = base_address + i * data_type_size

• 对于 m * n 的数组，a[i][j]_address = base_address + ( i * n + j) * data_type_size

链表（Linked List）

• 通过“指针”将一组零散的内存块串联起来使用

• 和数组相比，链表更适合插入、删除操作频繁的场景

• 最常见的链表结构：单链表、双向链表、循环链表

• 不带头结点的链表，初始时 head 等于 null；带头结点的链表，初始时 head->next 等于 null

应用场景

• 基于链表实现 LRU 缓存淘汰算法
  • 维护一个按照访问时间从大到小有序排列的链表，越靠近链表尾部的结点是越早之前访问的，当有一个数据被访问时，
  • 如果此数据已经在链表中了，将其删除，再插入到链表的头部
  • 如果此数据没有在链表中了：如果此时缓存未满，直接插入到链表的头部；如果此时缓存已满，则将链表尾结点删除，再插入到链表的头部

常见的链表操作

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第 n 个结点
• 求链表的中间结点

常见技巧：

1. 利用快慢指针（有时候需要用到三个指针），如找中间结点、链表中环的检测、删除倒数第 n 个节点
2. 利用哨兵简化实现难度。针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理，这时可以引入哨兵结点，即构建一个虚假的链表头（带头链表）
3. 留意边界条件处理，如链表为空、链表只包含一个结点、链表只包含两个结点，处理头结点和尾结点

例：判断一个字符串是否是回文字符串，字符串通过单链表来存储

• 使用快慢两个指针找到链表中点，慢指针每次前进一步，快指针每次前进两步。
• 在慢指针前进的过程中，同时修改其 next 指针，使得链表前半部分反序。
• 最后比较中点两侧的链表是否相等（同时对前半部分逆序复原）。

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) {
      return true;
    }
    
    ListNode prev = null;
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
      fast = fast.next.next;
      ListNode next = slow.next;
      slow.next = prev;
      prev = slow;
      slow = next;
    }
    
    if (fast != null) {
      slow = slow.next;
    }
    
    while (slow != null) {
      if (slow.val != prev.val) {
        return false;
      }
      slow = slow.next;
      prev = prev.next;
    }
    
    return true;
}

栈（Stack）

• 一种“操作受限”的线性表，只允许在一端插入和删除数据
• 后进者先出（LIFO），先进者后出
• 只支持：入栈 push、出栈 pop
• 栈既可以用数组来实现，也可以用链表来实现
• 入栈、出栈时间复杂度都是 O(1)
• 支持动态扩容的顺序栈，均摊时间复杂度分析是 O(1)

只关心上一次的操作；处理完上一次的操作后，能在 O(1) 时间内查找到更前一次的操作

应用场景

• 函数调用栈

  • 操作系统给每个线程分配了一块独立的内存空间，用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈

• 表达式求值

  • 通过两个栈来实现的。其中一个保存操作数的栈，另一个是保存运算符的栈。
  • 从左向右遍历表达式，当遇到数字，就直接压入操作数栈；当遇到运算符，就与运算符栈的栈顶元素进行比较。
  • 如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

• 表达式中括号是否匹配

  • 用栈来保存未匹配的左括号，从左到右依次扫描字符串。
  • 当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。

队列（Queue）

• 一种“操作受限”的线性表，只允许在队尾插入元素，在队头删除元素
• 先进者先出（FIFO）
• 只支持：入队 enqueue、出队 dequeue
• 队列可以用数组来实现（顺序队列），也可以用链表来实现（链式队列）
• 双端队列（Deque）：队列头尾两端都可以插入、删除数据
• 基于数组的循环队列
  • 队列为空的判断条件是 head == tail
  • 队满的判断条件是 (tail + 1) % n = head
  • 存储数据时会浪费一个存储单元，即 tail 指向的位置没有存储数据

• 阻塞队列：在队列为空时，从队头取数据会被阻塞；当队列已经满时，插入数据的操作会被阻塞
• 并发队列：线程安全的队列

应用场景

• 在有限资源池（如线程池、数据库连接池）中实现请求排队
• 用循环队列来实现滑动时间窗口限流算法

递归（recursion）

• 递归需要同时满足的三个条件：

  1. 一个问题的解可以分解为多个子问题的解
  2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
  3. 存在递归终止条件

• 写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码

• 注意事项：

  • 避免堆栈溢出，解决办法：第一种是限制递归深度；第二种是通过在堆上模拟实现一个函数调用栈，手动模拟递归压栈、出栈的过程
  • 避免重复计算，可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)
  • 避免无限递归，检测环是否存在

• 递归写法结构总结

  function fn(n) {
      // 第一步：判断输入或者状态是否非法？ (完整性检查)
      if(input/state is invalid) {
          return;
      }
  
      // 第二步：判读递归是否应当结束？
      if(match condition) {
          return some value;
      }
  
      // 第三步：缩小问题规模
      result1 = fn(n1);
      result2 = fn(n2);
  
      // 第四步: 整合结果
      return combine(result1, result2);
  }
  

所有的递归代码都可以改为迭代循环的非递归写法

递归时间复杂度的分析方法

• 递推公式
• 递归树

// 打印一组数据的所有排列
// 调用方式：
// int[] a = {1, 2, 3, 4}; printPermutations(a, 4, 4);
// k 表示要处理的子数组的数据个数
public static void printPermutations(int[] data, int n, int k) {
    if (k == 1) {
        for (int i = 0; i < n; ++i) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    for (int i = 0; i < k; ++i) {
        int tmp = data[i];
        data[i] = data[k-1];
        data[k-1] = tmp;

        printPermutations(data, n, k - 1);

        tmp = data[i];
        data[i] = data[k-1];
        data[k-1] = tmp;
    }
}

排序

• 分析排序算法的执行效率、内存消耗、稳定性
• 有序度是数组中具有有序关系的元素对的个数
• 完全有序的数组的有序度叫作满有序度，n(n-1)/2
• 逆序度 = 满有序度 - 有序度
• 排序的过程就是一种增加有序度，减少逆序度的过程，最后达到满有序度，就说明排序完成了

十大经典排序算法 (opens new window)

(opens new window)

均按从小到大排列
k 代表数值中的"数位"个数
n 代表数据规模
m 代表数据的最大值减最小值

n：数据规模
k：“桶”的个数
In-place：占用常数内存，不占用额外内存
Out-place：占用额外内存
稳定性：排序后相等元素之间原有的先后顺序不变

冒泡排序（Bubble Sort）

• 平均时间复杂度 O(n²)，空间复杂度 O(1)
• 对未排序的各元素从头到尾依次比较相邻的两个元素 arr[j]、arr[j + 1]
• 一次冒泡会让至少一个元素移动到它应该在的位置
• 当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作

public static void bubbleSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1); i++) {
        boolean hasChange = false; // 提前退出冒泡循环的标志位

        for (int j = 0; j < n - 1 - i; j++) { // -i 表示去掉排序好的元素
            if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
                swap(arr, j, j + 1); // 交换
                hasChange = true; // 表示此次冒泡有数据交换
            }
        }
        
        if (!hasChange) break;  // 没有数据交换，提前退出
    }
}

选择排序（Selection Sort）

• 平均时间复杂度 O(n²)，空间复杂度 O(1)
• 将数组中的数据分为两个区间，已排序区间和未排序区间（初始已排序区间只有一个元素，即数组的第一个元素）
• 每次从未排序区间中找到最小的元素，将其放到已排序区间的末尾
• 假定未排序序列的起始位置的元素 arr[i] 为最小值，依次去比较剩下的元素 arr[j]

public static void selectionSort(int[] arr) {
    int n = arr.length;

    for (int i = 0; i < n - 1; i++) {
        // 查找未排序区间最小值的位置
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        swap(arr, i, minIndex); // 交换
    }
}

插入排序（Insertion Sort）

• 平均时间复杂度 O(n²)，空间复杂度 O(1)
• 将数组中的数据分为两个区间，已排序区间和未排序区间（初始已排序区间只有一个元素，即数组的第一个元素）
• 取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入（即找到插入点后将插入点之后的元素顺序往后移动一位），并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空

冒泡排序和插入排序的时间复杂度都是 O(n²)，都是原地排序算法

冒泡排序中的元素交换需要 3 个赋值操作，而插入排序中的元素移动只需要 1 个赋值操作，所以插入排序要比冒泡排序更受欢迎

public static void insertionSort(int[] arr) {
    int n = arr.length;

    for (int i = 1; i < n; i++) {
        int current = arr[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; j--) {
            if(arr[j] > current) {
                arr[j + 1] = arr[j]; // 数据移动
            } else {
                break;
            }
        }
        arr[j + 1] = current; // 插入数据
    }
}

归并排序（Merge Sort）

• 使用分治思想
• 时间复杂度是 O(nlogn）
• 归并排序不是原地排序算法（合并函数无法在原地执行），空间复杂度是 O(n)
• 步骤：
  1. 把数组从中间划分成两个子数组；
  2. 一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素；
  3. 依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。

• 递推公式：sort(left … right) = merge(sort(left … mid), sort(mid+1 … right))
• 终止条件：left >= right，不再继续分解
• 其中 mid = (left + right)/2

public static void mergeSort(int[] arr) {
    sort(arr, 0, arr.length - 1);
}

private static void sort(int[] arr, int left, int right) {
    if (left >= right) return; // 是否只有一个元素

    // 取 left 到 right 之间的中间位置 mid，防止 (left+right) 的和超过 int 类型最大值
    int mid = left + (right - left) / 2;
    sort(arr, left, mid);
    sort(arr, mid + 1, right);

    // 将 arr[left ... mid] 和 arr[mid+1 ... right] 合并为 arr[left ... right]
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    // 申请一个大小跟 arr[left ... right] 一样的临时数组
    int[] tmp = new int[right - left + 1];
    int i = left; // 左子数组下标
    int j = mid + 1; // 右子数组下标
    int t = 0; // 临时数组下标

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            tmp[t++] = arr[i++];
        } else {
            tmp[t++] = arr[j++];
        }
    }

    while (i <= mid) { // 将左子数组剩余元素填充进 tmp 中
        tmp[t++] = arr[i++];
    }
    while (j <= right) { // 将右子数组剩余元素填充进 tmp 中
        tmp[t++] = arr[j++];
    }

    t = 0;
    // 将 tmp 中的元素全部拷贝到原数组中
    while (left <= right) {
        arr[left++] = tmp[t++];
    }
}

快速排序（Quick Sort）

• 使用分治思想
• 平均时间复杂度是 O(nlogn）
• 快速排序通过使用原地分区函数，可以实现原地排序，空间复杂度是 O(1)

• 步骤：
  1. 从数列中挑出一个元素，称为“基准”（pivot）。
  2. 分区（partition）操作：重新排序数列，所有元素比基准值小的放在基准前面，所有元素比基准值大的放在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序，递归的退出条件是数列的大小是 0 或 1。
• 递推公式：quick_sort(left … right) = quick_sort(left … p-1) + quick_sort(p+1… right)
• 终止条件：left >= right
• 其中 p = partition(arr, left, right)

关键：

1. 如何来选择分区点？最理想的分区点是被分区点分开的两个分区中，数据的数量差不多。常用的选择分区点的方法：三数取中法（arr[left]、arr[mid]、arr[right]）、随机法
2. 如何将大于 pivot 和小于 pivot 的元素进行划分？

• 分界游标 i ，前面的区间都是小于 pivot 的
• 遍历游标 j，一直往前走，遍历到某个数时，如果小于 pivot，那么就跟当前的游标 i 进行数字交换，交换后游标 i++

public static void quickSort(int[] arr) {
    srot(arr, 0, arr.length - 1);
}

private static void srot(int[] arr, int left, int right) {
    if (left >= right) return; // 是否只有一个元素

    int p = partition(arr, left, right); // 获取划分后分区点应该在的位置
    srot(arr, left, p - 1);
    srot(arr, p + 1, right);
}

// 单轴快排
private static int partition(int[] arr, int left, int rigth) {
    swap(arr, randRange(left, rigth), rigth); // 随机法
    int pivot = arr[rigth]; // 选择最后一个数据作为分区点
    int i = left;
    for (int j = left; j < rigth; j++) {
        // 将小于 pivot 的元素与 arr[i] 交换，交换后 i++
        if (arr[j] < pivot) {
            if (i != j) {
                swap(arr, i, j);
            }
            i++;
        }
    }

    swap(arr, i, rigth);

    return i;
}

线性时间复杂度排序算法

桶排序（Bucket Sort）

• 将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
• 对要排序数据的要求
  • 要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序
  • 数据在各个桶之间的分布是比较均匀的
• 桶排序比较适合用在外部排序中，即数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中

例：按订单金额（假设金额都是正整数）将 10GB 的订单数据进行排序

1. 先扫描一遍订单，根据订单的金额，将 10GB 的文件划分为几个金额区间。
2. 比如订单金额为 1 到 100 元的放到一个小文件，101 到 200 之间的放到另一个文件，以此类推，这样每个小文件都可以单独加载到内存排序。
3. 最后将这些有序的小文件合并，就是最终有序的 10GB 订单数据了

计数排序（Counting Sort）

• 当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
• 桶排序的一种特殊情况
• 桶内存储的是对应数据值的个数

• 计数排序只能用在数据范围不大的场景中，且只能给非负整数排序（要求元素能够作为数组的下标）

例：根据年龄给 100 万用户排序，按照成绩给 50 万考生排序

基数排序（Radix sort）

• 对要排序数据的要求
  • 要求数据可以划分成高低位，位之间有递进关系。比较两个数时，只需要比较高位，高位相同的再比较低位。
  • 每一位的数据范围不能太大，因为基数排序算法需要借助桶排序或者计数排序来完成每一个位的排序工作

例：将 10 万个手机号码从小到大排序
先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。（注意：这里按照每位来排序的排序算法要是稳定的）

二分查找（Binary Search）/二分搜索/折半查找

• 每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0
• 从有序数组中查找 val 出现的位置
• 前提：数组的元素是有序排列的，且数据是静态的
• 时间复杂度为 O(logn)

注意：终止条件、区间上下界更新方法、返回值选择

// 区间位置：如果 arr[mid] != target，下一次是以 mid + 1 作为下一个起始位置，或者 mid - 1 作为下一个结束位置
// 退出循环的条件：low > high
// mid 的计算方式：为防止溢出，low + (high - low) / 2 或 low + ((high - low) >> 1)
public static int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            // 查找第一个值等于给定值的元素
            if (mid == 0 || arr[mid - 1] != target) {
                return mid;
            } else {
                high = mid - 1;
            }

            // 查找最后一个值等于给定值的元素
            // if ((mid == arr.length - 1 || arr[mid + 1] != target)) {
            //     return mid;
            // } else {
            //     low = mid + 1;
            // }
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

// 查找第一个大于等于给定值的元素
public int binarySearch(int[] arr, int target) {
    int low = 0;
    int high = arr.length - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] >= target) {
            if ((mid == 0) || (arr[mid - 1] < target)) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

// 二分查找的递归实现
public static int binarySearch(int[] arr, int target) {
    return bsearchInternally(arr, 0, arr.length - 1, target);
}

private static int bsearchInternally(int[] arr, int target, int low, int high) {
    if (low > high) return -1;

    int mid = low + ((high - low) >> 1);
    if (arr[mid] == target) {
        return mid;
    }
    if (arr[mid] > target) {
        high = mid - 1;
    } else {
        low = mid + 1;
    }
	return bsearchInternally(arr, target, low, high);
}

• 四种常见的二分查找变形问题
  1. 查找第一个值等于给定值的元素
  2. 查找最后一个值等于给定值的元素
  3. 查找第一个大于等于给定值的元素
  4. 查找最后一个小于等于给定值的元素

跳表（Skip List）

• 使用空间换时间的设计思路，通过在链表上构建多级索引来提高查询的效率，实现了基于链表的“二分查找”
• 跳表是一种动态数据结构，支持快速地插入、删除、查找操作，时间复杂度都是 O(logn)
• 跳表的空间复杂度是 O(n)

按照区间来查找数据这个操作，红黑树的效率没有跳表高

散列表（Hash Table）

• 通过散列函数把元素的键映射为下标，然后将值存储在数组中对应下标的位置

• 散列函数的设计，应尽可能让散列后的值随机且均匀分布

• 装载因子（load factor）=填入表中的元素个数/散列表的长度

• 超过装载因子阈值时的动态扩容策略

  • 渐进式扩容：当装载因子触达阈值之后，只申请新空间，但并不将老的数据搬移到新散列表中。当有新数据要插入时，将新数据插入新散列表中，并从老的散列表中拿出一个数据放入到新散列表。

• 常用的散列冲突解决方法

  1. 开放寻址法（open addressing）

     • 如果出现了散列冲突，就重新探测一个空闲位置，将其插入
     • 探测方法，如线性探测（Linear Probing）、二次探测（Quadratic probing）、双重散列（Double hashing）
     • 当数据量比较小、装载因子小的时候，适合采用开放寻址法。如 Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突

  2. 链表法（chaining）

     • 在散列表中，每个“桶（bucket）”或者“槽（slot）”会对应一条链表，所有散列值相同的元素都放到相同槽位对应的链表中
     • 基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且支持更多的优化策略，比如用红黑树代替链表

     

散列表和链表（或跳表）结合使用

• 将散列表和链表（或跳表）结合使用，可以按照插入顺序遍历散列表中的数据，如

  • 基于散列表和双向链表实现 LRU 缓存淘汰算法
  • LinkedHashMap
  • Redis 有序集合，散列表+跳表

• 每个结点会在两条链中：一个链是双向链表，另一个链是散列表中的拉链
• 前驱指针（prev）、后继指针（next）是为了将结点串在双向链表中，hnext 指针是为了将结点串在散列表的拉链中

哈希算法

• 将任意长度的二进制值串映射为固定长度的二进制值串，这个映射的规则就是哈希算法
• MD5 的哈希值是 128 bit 长度，可以转化成 16 进制编码
• MurmurHash 算法 (opens new window)（计算速度快、冲突概率小），可以产生出 32 bit 或 128 bit 哈希值，应用软件：Redis、MemCache、Cassandra、HBase、Lucene 等

常见应用

• 安全加密

• 唯一标识（信息摘要）

  • 在海量的图库中，搜索一张图是否存在：从图片的二进制码串开头取 100 个字节，从中间取 100 个字节，从最后再取 100 个字节，然后将这 300 个字节放到一块，通过哈希算法（比如 MD5），得到一个哈希字符串，用它作为图片的唯一标识。通过这个唯一标识来判定图片是否在图库中。

• 校验数据的完整性和正确性

• 散列函数

• 负载均衡

  • 实现会话粘滞（session sticky）的负载均衡算法，即同一次会话中的所有请求都路由到同一个服务器上

• 数据分片

  • 针对海量数据，先对数据进行分片，然后采用多台机器处理的方法，来提高处理速度

• 分布式存储

  • 利用一致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据大量搬移的难题

树（Tree）

• 无向、连通的无环图
• 父节点、子节点、兄弟节点（父节点相同）、根节点（没有父节点）、叶子节点（没有子节点）
• 结点的度（degree）：结点的子树个数
• 树的度：树的所有结点中最大的度数
• 节点的高度（height）= 节点到叶子节点的最长路径（边数）
• 节点的深度（depth）= 根节点到该节点所经历的边的个数
• 节点的层（level）= 节点的深度 + 1
• 树的高度 = 根节点的高度

二叉树（Binary Tree）

• 每个节点最多有两个子节点，分别是左子节点和右子节点

• 满二叉树：除了叶子节点之外，每个节点都有左、右两个子节点

• 完全二叉树：除了最后一层，其它层的节点个数都是满的，且最后一层的叶子节点都靠左排列

• 二叉树的存储方法：

  • 基于指针或者引用的链式存储法

    

  • 基于数组的顺序存储法

    

    • 从数组下标为 1 开始存储数据时，下标为 i 的节点，左子节点下标为 i∗2，右子节点下标为 i∗2 + 1，父节点下标为 i/2
    • 从数组下标为 0 开始存储数据时，下标为 i 的节点，左子节点下标为 i∗2 + 1，右子节点下标为 i∗2 + 2，父节点下标为 (i-1)/2
    • 对于完全二叉树，下标从 n/2 + 1 到 n的节点都是叶子节点

    • 数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间

• 二叉树的遍历，时间复杂度是 O(n)，节点的个数 n

  

  • 前序遍历的递推公式（根左右）：preOrder(r) = print r -> preOrder(r.left) -> preOrder(r.right)
  • 中序遍历的递推公式（左根右）：inOrder(r) = inOrder(r.left) -> print r -> inOrder(r.right)
  • 后序遍历的递推公式（左右根）：postOrder(r) = postOrder(r.left) -> postOrder(r.right) -> print r

二叉查找树（Binary Search Tree）

• 二叉查找树中，每个节点的值都大于或等于左子树节点的值，小于或等于右子树节点的值
• 中序遍历二叉查找树，可以输出有序的数据序列
• 插入、删除、查找等操作的时间复杂度跟树的高度成正比，O(height)

• 散列表对比二叉查找树：
  1. 散列表有序输出困难，需要额外排序；
  2. 散列表扩容代价比较大；
  3. 散列表查询效率不一定比二叉树高（散列冲突，散列函数计算）；
  4. 散列表构造更复杂；
  5. 为避免过多散列冲突，装载因子不能太大，浪费内存。

平衡二叉查找树

• 平衡二叉树：二叉树中任意一个节点的左右子树的高度相差不能大于 1
• 为了解决普通二叉查找树在数据更新的过程中，复杂度退化的问题而产生
• 平衡二叉查找树的高度接近 log~2~n，所以插入、删除、查找操作的时间复杂度也比较稳定，是 O(logn)
• 如：AVL 树

红黑树

• 红黑树 Red-Black Tree（简称 R-B Tree），一种不严格的平衡二叉查找树，降低维护平衡的成本

• 需要满足的要求：

  1. 根节点是黑色的；
  2. 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
  3. 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
  4. 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；

更倾向用跳表来替代红黑树

堆（Heap）

• 堆是一种完全二叉树

• 最大的特性：堆中每个节点的值都大于等于（或小于等于）其子树中每个节点的值

• 堆被分成了两类：大顶堆、小顶堆

• 堆的两个常用操作，时间复杂度都是 O(logn)

  • 插入一个数据时，把新插入的数据放到数组的最后，然后从下往上堆化
  • 删除堆顶数据时，把数组中的最后一个元素放到堆顶，然后从上往下堆化

  

  

• 堆化：顺着节点所在的路径，向上或者向下，对比，然后交换

堆的应用

1. 基于堆实现排序

   • 时间复杂度是 O(nlogn)，空间复杂度是 O(1)
   • 不是稳定的排序算法
   • 堆排序包含两个过程，建堆和排序
     1. 建堆：将下标从 n/2 到 1 的非叶子节点（假设堆中的数据是从数组下标为 1 的位置开始存储），依次进行从上到下的堆化操作，将数组中的数据组织成堆。时间复杂度是 O(n)
     2. 排序：迭代地将堆顶的元素交换到堆的末尾，并将堆的大小减一，然后再堆化，重复这个过程，直到堆中只剩下一个元素。时间复杂度是 O(nlogn)

2. 优先级队列

   • 优先级高的数据先出队
   • Java 中的 PriorityQueue（小顶堆）

   1. 合并有序小文件
      从各个小文件中取出第一个字符串放入到小顶堆中，将堆顶的数据放入到大文件中，删除堆顶数据，再从存储了原被删堆顶数据的小文件中取出下一个字符串放入到堆中，重复这个过程

   2. 高性能定时器
      按照任务设定的执行时间，将这些任务存储在优先级队列中，定时器取优先级队列中队首任务的执行时间点得到时间间隔 T

3. 求 Top K

   • 在一个包含 n 个数据的数组中，查找前 K 大数据
   • 维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出数据，把堆填满后，与堆顶元素比较
   • 如果比堆顶元素大，就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组
   • 时间复杂度是 O(nlogK)

4. 求中位数或其它百分位数

   • 求 n 个数据的 99 百分位数
   • 维护两个堆，一个大顶堆，一个小顶堆，加入新数据时，调整两个堆，使得：
     • 1. 大顶堆中保存 n*99% 个数据，小顶堆中保存 n*1% 个数据
     • 2. 小顶堆中的数据都大于大顶堆中的数据
   • 如果新加入的数据小于等于大顶堆的堆顶元素，将这个新数据插入到大顶堆；否则，就将这个新数据插入到小顶堆
   • 计算大顶堆和小顶堆中的数据个数是否还符合 99:1，如果不符合，就将一个堆中的堆顶元素移动到另一个堆，直到满足这个比例
   • 大顶堆的堆顶元素就是要求的数据

例：在一个包含 10 亿个搜索关键词的日志文件，如何能快速获取到热门榜 Top 10 的搜索关键词

• 处理的场景：单机，可以使用的内存为 1GB
• 假设 10 亿条搜索关键词中不重复的有 1 亿条，每个搜索关键词的平均长度是 50 个字节
• 步骤：
  1. 将 10 亿条搜索关键词先通过哈希算法分片到 10 个文件中：通过某个哈希算法对其求哈希值，然后哈希值同 10 取模，得到应该被分到的文件编号（散列表大小为 50 亿字节（5GB > 1GB），所以需要分片；确保同一个搜索关键词在相同文件中）
  2. 针对每个分片后到文件，利用散列表和堆，分别求出 Top 10：顺序扫描文件中的搜索关键词，利用散列表记录搜索关键词及其出现的次数；建立一个大小为 10 的小顶堆，遍历散列表，依次取出每个搜索关键词及对应出现的次数，然后与堆顶的搜索关键词对比，如果出现次数比堆顶搜索关键词的次数多，就删除堆顶的关键词，将这个出现次数更多的关键词加入到堆中
  3. 把这个 10 个 Top 10 放在一起，然后取这 100 个关键词中，出现次数最多的 10 个关键词

B+ 树（B+ Tree）

• B+ 树是一个多叉树，其的特点（m 表示树的度）：

  1. 每个节点中子节点的个数不能超过 m，也不能小于 m/2
  2. 根节点的子节点个数可以不超过 m/2，这是一个例外
  3. m 叉树只存储索引，并不真正存储数据（类似跳表）
  4. 通过双向链表将叶子节点串联在一起，方便按区间查找
  5. 一般情况，根节点会被存储在内存中，其他节点存储在磁盘中

• B 树只是一个每个节点的子节点个数不能小于 m/2 的 m 叉树

• B- 树就是 B 树，英文翻译都是 B-Tree，B 树跟 B+ 树的不同点：

  1. B+ 树中的节点不存储数据，只是索引，而 B 树中的节点存储数据
  2. B 树中的叶子节点并不需要链表来串联

不管是内存中的数据，还是磁盘中的数据，操作系统都是按页来读取的，一次会读一页的数据。一页大小通常是 4KB，可以通过 getconf PAGE_SIZE 命令查看。

在选择 m 大小的时候，要尽量让每个节点的大小等于一个页的大小。读取一个节点，只需要一次磁盘 IO 操作。

/**
 * 这是B+树非叶子节点的定义。
 *
 * 假设keywords=[3, 5, 8, 10]
 * 4个键值将数据分为5个区间：(-INF,3), [3,5), [5,8), [8,10), [10,INF)
 * 5个区间分别对应：children[0]...children[4]
 *
 * m值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = (m-1)*4[keywordss大小]+m*8[children大小]
 */
public class BPlusTreeNode {
    public static int m = 5; // 5叉树
    public int[] keywords = new int[m-1]; // 键值，用来划分数据区间
    public BPlusTreeNode[] children = new BPlusTreeNode[m]; // 保存子节点指针
}

/**
 * 这是B+树中叶子节点的定义。
 *
 * B+树中的叶子节点跟内部节点是不一样的,
 * 叶子节点存储的是值，而非区间。
 * 这个定义里，每个叶子节点存储3个数据行的键值及地址信息。
 *
 * k值是事先计算得到的，计算的依据是让所有信息的大小正好等于页的大小：
 * PAGE_SIZE = k*4[keyw..大小]+k*8[dataAd..大小]+8[prev大小]+8[next大小]
 */
public class BPlusTreeLeafNode {
    public static int k = 3;
    public int[] keywords = new int[k]; // 数据的键值
    public long[] dataAddress = new long[k]; // 数据地址

    public BPlusTreeLeafNode prev; // 这个结点在链表中的前驱结点
    public BPlusTreeLeafNode next; // 这个结点在链表中的后继结点
}

图（Graph）

• 有向图、无向图

• 带权图

• 顶点的度（degree）：跟顶点（vertex）相连接的边（edge）的条数

• 在有向图中，度分为入度（in-degree）、出度（out-degree）

• 图的两个主要的存储方式

  

  

  • 邻接矩阵（Adjacency Matrix）：底层是一个二维数组
  • 邻接表（Adjacency List）：每个顶点都对应一个链表，存储与其相连接的其它顶点
    • 有向图中邻接表是顶点的出度表，逆邻接表是顶点的入度表

  邻接矩阵存储方法的缺点是比较浪费空间，但是优点是查询效率高，而且方便矩阵运算；邻接表的存储方式比较节省存储空间，但链表不方便查找

图上的搜索算法

• 图上的搜索算法，在图中找出从一个顶点出发，到另一个顶点的路径

BFS、DFS 仅适用于图不大的情况，时间复杂度都是 O(E)，空间复杂度都是 O(V)，其中 V 表示顶点的个数，E 表示边的个数

广度优先搜索（BFS）

• 广度优先搜索 Breadth-First-Search
• 一般用来解决最短路径的问题
• 优先遍历邻居节点
• 从起点出发，逐层往外遍历，每层当中的点距离起点的步数都是相同的
• 需要借助队列来实现
• 双端 BFS：同时从起点和终点开始进行的广度优先搜索，可以高搜索的效率

深度优先搜索（DFS）

• 深度优先搜索 Depth-First-Search
• 解决的是连通性的问题：判断是否有一条路径能从起点连接到终点
• 优先遍历子节点
• 算法思想（回溯）：
  1. 从起点出发，选择一个可选方向不断向前，直到无法继续为止
  2. 然后尝试另外一种方向，直到最后走到终点
• 借助栈来实现

位图（Bit Map）

• bit 数组
• Java 中的 BitSet 类
• 压缩位图（Comprised bitmap）：Roaring bitmaps (opens new window)，不适用取值范围小或数据排列稀疏/随机的场景

布隆过滤器（Bloom Filter）

• 实际上是一个 bit 数组，使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值对应的 bit 位置 1
• 如果某个数字经过布隆过滤器判断不存在，那说明这个数字一定不存在；如果某个数字经过布隆过滤器判断存在，这时有可能会误判，有可能并不存在。（False is always false. True is maybe true.）
• 适合不需要 100% 准确的、允许存在小概率误判的大规模判重场景，如大型网站的每天的 UV 数、网页爬虫中的 URL 去重
• 扩容：当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，就重新申请一个新的位图，后面来的新数据，会被放置到新的位图中。要判断某个数据是否在布隆过滤器中已经存在，就需要查看多个位图。
• Bloom Filter Calculator (opens new window)
• com.google.common.hash.BloomFilter

1 亿个二进制位 ≈ 12MB

构建索引常用的数据结构

支持动态数据集合的数据结构：散列表、红黑树、跳表、B+ 树

• 散列表增删改查操作的性能非常好，时间复杂度是 O(1)。一些键值数据库，比如 Redis、Memcache，就是使用散列表来构建索引的。这类索引，一般都构建在内存中。
• 红黑树作为一种常用的平衡二叉查找树，数据插入、删除、查找的时间复杂度是 O(logn)，也非常适合用来构建内存索引。Ext 文件系统中，对磁盘块的索引，用的就是红黑树。
• B+ 树比起红黑树来说，更加适合构建存储在磁盘中的索引。B+ 树是一个多叉树，所以，对相同个数的数据构建索引，B+ 树的高度要低于红黑树。当借助索引查询数据的时候，读取 B+ 树索引，需要的磁盘 IO 次数会更少。所以，大部分关系型数据库的索引，比如 MySQL、Oracle，都是用 B+ 树来实现的。
• 跳表也支持快速添加、删除、查找数据。通过调整索引结点个数和数据个数之间的比例，可以平衡索引对内存的消耗及其查询效率。Redis 中的有序集合，就是用跳表来构建的。
• 位图、布隆过滤器可以作为辅助索引。构建一个布隆过滤器，并且存储在内存中。查询数据时，先通过布隆过滤器，判定是否存在，如果通过布隆过滤器判定数据不存在，没有必要读取磁盘中的索引了。
• 有序数组可以用来对静态数据构建索引。如果数据是静态的（即不会有插入、删除、更新操作），可以把数据的关键词（查询用的）抽取出来，组织成有序数组，然后利用二分查找算法来快速查找数据。

字符串匹配算法

• 主串、子串
• 模式串
• n、m 表示主串和模式串的长度

单模式串匹配算法

• 在一个模式串和一个主串之间进行匹配

BF 算法（Brute Force 算法）

• BF 算法是最简单、粗暴的字符串匹配算法，实现思路是，拿模式串与主串中是所有子串匹配，看是否有能匹配的子串。
• 时间复杂度是 O(n*m)

RK 算法（Rabin-Karp 算法）

• RK 算法是借助哈希算法对 BF 算法进行改造，即对每个子串分别求哈希值，然后拿子串的哈希值与模式串的哈希值比较，减少了比较的时间。
• 时间复杂度是 O(n)，极端情况下，哈希算法大量冲突，时间复杂度退化为 O(n*m)

BM 算法（Boyer-Moore 算法）

• BM 算法核心思想是，利用模式串本身的特点，在模式串中某个字符与主串不能匹配的时候，将模式串往后多滑动几位，以此来减少不必要的字符比较，提高匹配的效率

KMP 算法（Knuth-Morris-Pratt 算法）

• 与 BM 算法的本质类似，都是根据规律在遇到坏字符的时候，把模式串往后多滑动几位
• 只需要一个额外的 next 数组，空间复杂度是 O(m)
• 时间复杂度是 O(m+n)

多模式串匹配算法

• 在一个主串中同时查找多个模式串

Trie 树（字典树/前缀树）

• 一种专门处理字符串匹配的数据结构（多叉树），用来解决在一组字符串集合中快速查找某个字符串的问题

• Trie 树的本质，是利用字符串之间的公共前缀，将重复的前缀合并在一起

• 比较耗内存，是一种空间换时间的思路

• Trie 树的两个操作：

  • 将字符串集合构造成 Trie 树，即将字符串插入到 Trie 树。时间复杂度是 O(n)，n 表示所有字符串的长度和。

    

    通过数组存储一个节点的所有子节点的指针：假设字符串中只有从 a 到 z 这 26 个小写字母，在数组中下标为 0 的位置存储指向子节点 a 的指针，以此类推。

  • 在 Trie 树中查询一个字符串。时间复杂度是 O(k)，k 表示要查找的字符串的长度。

• 比较适合查找前缀匹配的字符串，如：搜索引擎中的关键词提示、自动输入补全

AC 自动机算法（Aho-Corasick 算法）

• 适合大量文本中多模式串的精确匹配查找，如敏感词过滤

贪心算法（greedy agorithm）

• 是否可以用贪心算法解决：每次选择的数据是，当前情况下，在对限制值同等贡献量的情况下，对期望值贡献最大的数据
• 在每一步选中都采取在当前状态下最好或最优的选择，从而希望导致结果是最好或最优的
• 能用贪心算法解决的问题，需要满足三个特征：最优子结构、无后效性、贪心选择性（即通过局部最优的选择，能产生全局的最优选择）
• 贪心算法并不一定能得到最优解
• 经典的应用场景：霍夫曼编码（Huffman Coding）、Prim 和 Kruskal 最小生成树算法、Dijkstra 单源最短路径算法

分治算法（divide and conquer）

• 将原问题划分成 n 个规模较小，并且结构与原问题相似的子问题，递归地解决这些子问题，然后再合并其结果，就得到原问题的解。
• 分治算法是一种处理问题的思想，递归是一种编程技巧
• 分治算法的递归实现中，每一层递归都会涉及以下三个操作：
  1. 分解：将原问题分解成一系列子问题
  2. 解决：递归地求解各个子问题，若子问题足够小，则直接求解
  3. 合并：将子问题的结果合并成原问题。
• 典型的应用场景：指导编码，降低问题求解的时间复杂度；解决海量数据处理问题，如 MapReduce

回溯算法（backtracking agorithm）

• 把问题求解的过程分为多个阶段，每个阶段都会面对一个岔路口，先随意选一条路走，当发现这条路走不通的时候（不符合期望的解），就回退到上一个岔路口，另选一种走法继续走
• 回溯算法适合用递归代码实现；在实现的过程中，剪枝操作是提高回溯效率的一种技巧
• 基本上能用的动态规划、贪心解决的问题，都可以用回溯算法解决
• 时间复杂度 O(2^n^)
• 典型的应用场景：深度优先搜索、八皇后、数独、0-1 背包、图的着色、旅行商问题、全排列、正则表达式匹配等

动态规划（dynamic programming）

• 能用动态规划解决的问题，要求问题可以抽象成分阶段决策最优解模型（一个模型），且需要满足三个特征：
  1. 最优子结构：可以通过子问题的最优解，推导出问题的最优解
  2. 无后效性
  3. 存在重复子问题：不同的决策序列，到达某个相同的阶段时，可能会产生重复的状态
• 动态规划是一种空间换时间的算法思想
• 动态规划的两种解题思路
  1. 状态转移表法：回溯算法实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码
  2. 状态转移方程法：找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码

拓扑排序（topological sorting）

• 基于有向无环图的算法
• 凡是需要通过局部顺序来推导全局顺序的，一般都能用拓扑排序来解决（确定依赖关系）
• 检测图中环的存在
• 实现方法：Kahn 算法、DFS 深度优先搜索算法
• 时间复杂度都是 O(V+E)（V 表示顶点个数，E 表示边的个数）

Kahn 算法

• 用的是贪心算法思想
• 步骤：
  1. 先从图中找出一个入度为 0 的顶点，将其输出到拓扑排序的结果序列中，并且把这个顶点从图中删除（即把这个顶点可达的顶点的入度都减 1）；
  2. 循环执行上面的过程，直到所有的顶点都被输出；
  3. 最后得到的序列，就是满足局部依赖关系的拓扑排序。

DFS 算法

最短路径（shortest path）

• 在一个有向有权图中，求两个顶点间的最短路径
• 最短路径算法：Dijkstra 算法、Bellmam-Ford 算法、Floyd 算法等

启发式搜索（heuristically search）

• 启发式搜索算法：A* 算法、IDA* 算法、蚁群算法、遗传算法、模拟退火算法等

---

1 Byte（字节） = 8 bit（比特）
100 万字节 ≈ 1MB
1 亿字节 ≈ 100MB
10 亿字节 ≈ 1GB
1 亿个二进制位 ≈ 12MB
2³²Bit = 512MB
2⁶⁴Bit = 2097152TB
2³¹ ≈ 21 亿

---